With the increasing demand for video telephony, video conferencing, and multimedia, full motion video on computer generated displays has become an important topic in recent times. A major aspect of full motion video which sets it apart from other types of computer generated displays is that it requires an exceptionally high rate of information transfer between the data source and the display mechanism. This high transfer rate is needed in order to refresh the display at a sufficient rate so as to provide a moving image which is reasonably clear and free of "fuzzy" edges. Currently, however, due to transmission line and hardware constraints, it is not possible to transfer data in a regular format at a sufficient rate to provide a clear moving image. As a result, data compression techniques are typically implemented to transfer more information in shorter periods of time. In addition to full motion video displays, data compression may also be implemented in other applications such as in audio transmissions, communications, compressed data storage, network applications, and various other applications which have bandwidth limitations. Thus, data compression has wide applicability.
One compression method which is currently employed involves the use of variable length encoding and decoding. The basic concept underlying variable length coding, or statistical coding as it is sometimes known, is that data which occurs most frequently should be assigned a code having the fewest number of bits, and data which occurs least frequently should be assigned a code having the largest number of bits. Statistical coding makes it highly probable that most information will be encoded using short codes with only a small portion being represented by long codes. On average, significantly more information can be contained in a specified number of bits using variable length codes rather than fixed length codes.
Data compression using variable length codes may be implemented in a number of different encoding/decoding schemes, including schemes which encode fixed length data words into variable length data strings (fixed-to-variable), schemes which encode variable length data words into fixed length data strings (variable-to-fixed), and schemes which encode variable length data words into variable length data strings (variable-to-variable). Within these schemes, encoding and decoding may be carried out in various ways. One way in which decoding is carried out in a fixed-to-variable scheme involves the use of a finite state machine or a decoding tree. According to this method, an incoming data stream is decoded one bit at a time until a complete encoded data string is decoded. Thereafter, the process is repeated to decode the next data string in the data stream. This method decodes the incoming data properly; however, it is unacceptably slow in that it decodes only one bit per decoding cycle. A faster implementation involves the use of a look-up table. In this implementation, decoding information is stored in a memory, and this information is accessed by applying the incoming bit stream or a portion thereof as an address to the memory. The use of a look-up table allows one data string to be decoded per decoding cycle. While the look-up tables which are currently used provide significant performance improvement over the decoding tree, they are limited in that at most one data string is decoded per decoding cycle, regardless of how the data strings are arranged in the incoming data stream. A more desirable method would be one which recognizes certain combinations of data strings in the data stream, and takes advantage of these combinations to decode more than one data string per cycle. Currently, however, there is no mechanism believed to be available which has this capability.